//
// Description: 174. 地下城游戏
// Created by Loading on 2022/6/15.
//

#include <bits/stdc++.h>

using namespace std;

int calculateMinimumHP(vector<vector<int>> &dungeon) {
    int m = dungeon.size();
    int n = dungeon[0].size();

    // dp[i][j] 表示在 (i,j) 位置的最小体力值
    int dp[m + 1][n + 1];
    memset(dp, 0x3f, sizeof dp);

    dp[m - 1][n] = dp[m][n - 1] = 1;

    // 倒序dp
    for (int i = m - 1; i >= 0; --i) {
        for (int j = n - 1; j >= 0; --j) {
            // 由右侧或下侧格子状态转移
            dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
            /* 注意：在任何时候，体力值都不可小于等于 0 */
            dp[i][j] = max(dp[i][j], 1);
        }
    }

    return dp[0][0];
}

int main() {
    vector<vector<int>> dungeon{{-2, -3,  3},
                                {-5, -10, 1},
                                {10, 30,  -5}};

    auto res = calculateMinimumHP(dungeon);

    cout << res << endl;

    return 0;
}